/**
 * 如题。在最大子段和的基础上只需要考虑同时选中头尾的情况
 * 
 * 同时选中头尾本质上就是求前缀与后缀的最大和
 * 可以使用预处理前缀和，然后枚举后缀和解决
 */
using vi = vector<int>;

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        return max(maxSubArray(nums), kua(nums));        
    }

    int maxSubArray(const vector<int> & nums) {
        N = nums.size();
        D.assign(N, 0);
        U.assign(N, 0);
        D[0] = U[0] = nums[0];
        for(int i=1;i<N;++i){
            U[i] = max(U[i - 1] + nums[i], nums[i]);
            D[i] = max(D[i - 1], U[i]);
        }
        return D[N - 1];
    }   

    int kua(const vector<int> & nums){
        N = nums.size();
        S.assign(N, 0);
        M.assign(N, 0);
        S[0] = M[0] = nums[0];
        for(int i=1;i<N;++i){
            S[i] = S[i - 1] + nums[i];
            M[i] = max(M[i - 1], S[i]);
        }

        int hz = 0;
        int ans = nums[0] + nums[N - 1];
        for(int i=N-1;i>1;--i){
            hz += nums[i];
            ans = max(ans, hz + M[i - 2]);
        }
        return ans;
    }

int N;
vi D;
vi U;
vi S;
vi M;

};
